强化学习中的数学原理（二）：贝尔曼最优方程与迭代算法

在理解了基础的贝尔曼期望方程能够系统地评估一个策略的价值之后，我们需要进一步解决强化学习中的关键问题：如何找到最优的策略。

本篇将通过数学推导介绍贝尔曼最优方程 (Bellman Optimality Equation, BOE)，并结合**收缩映射定理 (Contraction Mapping Theorem)**探讨最优策略的存在性与唯一性。在此基础上，进一步总结强化学习中基础的两种求解算法：值迭代 (Value Iteration) 与 策略迭代 Policy Iteration。

3. 最优策略与贝尔曼最优方程 (BOE)

最优策略 (Optimal Policy, $\pi^*$ ) 的定义是：对于环境中的任意状态 $s$ ，该策略下的状态价值大于或等于其他所有策略在该状态下的价值：

v_{\pi^*}(s) \ge v_\pi(s), \quad \forall s \in \mathcal{S} \text{ and } \forall \pi

这引出几个基本问题：

这样的最优策略是否存在？
最优策略是否唯一？
最优策略是确定性的 (Deterministic) 还是随机分布的 (Stochastic)？
如何计算出这个策略？

从策略提升推导 BOE

在评估策略时，动作价值函数 $q(s,a)$ 表示在状态 $s$ 下采取动作 $a$ 后，遵循当前策略的期望回报。通过观察 $q(s,a)$ ，我们可以评估在某个状态下改用其他动作是否有益。

策略改进例题分析

【策略改进评估分析】：从上图可以看出，在给定的基础策略下算出的 $v$ 值有时会掩盖个别更优动作的潜力。比如在该状态下计算出动作 $a_3$ 能带来更高的动作价值（即 $q$ 值大于当前的 $v$ 值）。如果我们在构建新策略时，在这类状态直接选择能使得 $q$ 值最大的动作（如 $a_3$ ），并使其概率为 1，就能得到一个价值回报不劣于原策略的新策略 $\pi_{new}$ 。

如果我们在方程式中直接引入这种“取最大化 (Maximization)”的思想，就能得到贝尔曼最优方程 (BOE)：

v_*(s) = \max_{\pi} \sum_{a \in \mathcal{A}} \pi(a|s) q_*(s,a)

为了使得上式中的期望最大化，我们可以在保证概率和为 1 的前提下，直接让最大化 $q_*(s,a)$ 的动作对应的概率为 1。因此，BOE 通常被化简为不包含 $\pi$ 的形式：

v_*(s) = \max_{a \in \mathcal{A}} \left[ r(s,a) + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) v_*(s') \right]

若写成矩阵或向量形式表示（由于 max 算子操作变为逐元素的最大化）：

V_* = \max_\pi (R_\pi + \gamma P_\pi V_*)

收缩映射定理 (Contraction Mapping Theorem)

在上述方程中包含了一个非线性的求最大值操作（max）。为了研究并求解这种非线性方程，我们需要引入收缩映射定理。

假设我们将方程右侧定义为一个映射算子 $f(V) = \max_\pi (R_\pi + \gamma P_\pi V)$ 。

收缩映射定理分析

【收缩映射定理推导解析】：引入距离度量（如最大绝对误差的 L-infinity 范数 $||V||_\infty$ ）后，可以从数学上证明，当折扣因子 $0 < \gamma < 1$ 时，每次经过算子 $f(V)$ 的映射计算，变量间的“距离”都会成比例地（即 $\gamma$ 倍）缩小。由于它符合收缩映射的条件，我们可以得出两个结论：

解的存在性与唯一性：存在唯一的不动点满足 $f(V_*) = V_*$ 。这说明理想中的最优状态价值函数是必定存在且唯一的。
迭代求解机制：无论赋予什么样的初值 $V_0$ ，只要反复将数值代入映射进行迭代计算，该数值就会持续向唯一的真实最优解靠拢，并以指数级收敛。

奖励和折扣因子对于策略的影响

环境参数如何影响我们最终求得的策略？

改变奖励 $r$ ：如果是将原始回报值变为 $ar+b \ (a>0)$ 的线性变化，由于不同操作的相对收益大小不会改变，最优策略的收敛结果依然保持一致。
改变折扣因子 $\gamma$ ： $\gamma$ 改变的是模型规划路线时的远视程度。 $\gamma$ 数值越小越“近视”，模型越趋向于避免眼前的惩罚而忽视长远的危险。因此这会直接导致策略发生偏转。

4. 求解最优策略：值迭代与策略迭代

在已有环境概率模型的前提下，基于收缩映射的可解性保证，强化学习发展出了两种基础的动态规划求解算法：值迭代 (Value Iteration) 和 策略迭代 Policy Iteration。

值迭代 (Value Iteration，VI)

在迭代过程中，值迭代不会显式地给出一个具体的策略分布向量。它通过不断更新状态价值本身逼近最优解：在第 $k$ 轮，我们拥有一个估算出的全局状态价值数组 $v_k$ （这只是一组用来迭代逼近的数值中转，而不是某个具体策略的 State value）。接下来，我们通过考虑所有后续可能的状态节点得到下一轮的新估值 $v_{k+1}$ 。

其迭代公式即为直接应用 BOE：

v_{k+1}(s) = \max_a \underbrace{\left( r(s,a) + \gamma \sum_{s'} p(s'|s,a) v_k(s') \right)}_{q_k(s,a)}, \quad \forall s \in \mathcal{S}

第一步，对于当前的数值 $v_k$ ，寻找能使动作价值 $q(s,a)$ 最大化的动作分支。第二步，利用该局部最大值赋为新一轮 $v_{k+1}$ 的值。不断重复执行更新，直到前后两轮差值足够小，从而判定为收敛。

值迭代算法详解

【值迭代工作流分析】：图中的迭代网络显示，下一轮（第 $k+1$ 轮）节点的更新必须基于上一轮算出的已知量 $v_k$ 开展运算。我们需要在已有 $v_k$ 的基础上，计算每个状态下选择不同动作分支得到的 $q_k(s,a)$ ，并从中选取最大值，更新至本状态，循环往复。

策略迭代 (Policy Iteration，PI) 与联系

与值迭代不同，策略迭代由两个步骤交替进行：

策略评估 (Policy Evaluation)：给定当前策略 $\pi_k$ 并将其固定，计算出确切收敛的对应状态价值 $V_{\pi_k}$ 。
策略提升 (Policy Improvement)：基于计算出的价值矩阵，在每个状态下用贪心法比较全部可选动作对应的 $q_{\pi_k}(s,a)$ 。如果有动作产生的值大于基础策略动作的值，即可修改策略并作为下一次评估的新准则 $\pi_{k+1}$ 。按照这套评估与提升规则，其必然会在有限步骤后收敛至于全局最优策略。

策略迭代与值迭代的联系

【Truncated Policy Iteration — 两算法之间的联系】：策略迭代和值迭代有着内在等效性。如果在策略迭代的评估步骤中，不强求等待价值函数精确收敛到 $V_{\pi_k}$ ，而是仅迭代更新一次（截断操作，Truncated）就转向策略提升并取贪心最优的动作。那么，这种修改版策略迭代流程所做出的更新计算，在数学形式与思路上就完全等同于值迭代 (Value Iteration)。依靠映射中的收缩机制保护，这套流程依旧能导向最后的正确答案。

目录